home *** CD-ROM | disk | FTP | other *** search
/ The 640 MEG Shareware Studio 2 / The 640 Meg Shareware Studio CD-ROM Volume II (Data Express)(1993).ISO / clang / jcool01.zip / BASE_BNT.C < prev    next >
C/C++ Source or Header  |  1992-08-20  |  17KB  |  482 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 07/19/89 -- Initial design and implementation
  13. // Updated: MBN 09/19/89 -- Added conditional exception handling
  14. // Updated: MJF 03/12/90 -- Added group names to RAISE
  15. // Updated: VDN 02/21/92 -- New lite version
  16. //
  17. // The Binary_Tree class implements the type-generic  structural methods of the
  18. // parameterized Binary_Tree<Type>  class  and is  a friend of  the Binary Node
  19. // class.  The  Binary_Tree   class  is  intended for  the    sole  use  of the
  20. // parameterized  Binary_Tree<Type>    class.    The    Binary_Tree<Type> class
  21. // implements simple,  dynamic,   sorted  sequences.  Users who  require a data
  22. // structure  for unsorted  sequences  whose structure and organization is more
  23. // under the control of the programmer are refered to the N_Tree class.
  24. //
  25.  
  26. #include <cool/Base_Binary_Tree.h>
  27.  
  28. #include <cool/Pair.C>
  29. #include <cool/Stack.C>
  30.  
  31. #define IGNORE(arg) (void) arg
  32.  
  33. // CoolBase_Binary_Tree -- Simple constructor to initialize a CoolBase_Binary_Tree object
  34. // Input:              None
  35. // Output:             None
  36.  
  37. CoolBase_Binary_Tree::CoolBase_Binary_Tree () {
  38.   this->root = NULL;                // Initialize root pointer
  39.   this->number_nodes = 0;            // Initialize node count
  40.   this->state.forward = TRUE;            // Assume Forward direction;
  41. }
  42.  
  43.  
  44. // ~CoolBase_Binary_Tree -- destructor must be virtual to delete both state and data.
  45. // Input:              None
  46. // Output:             None
  47.  
  48. CoolBase_Binary_Tree::~CoolBase_Binary_Tree () {}        // state is deleted automatically
  49.  
  50.  
  51. // clear -- removes root and all subtrees
  52. // input -- none
  53. // output -- none
  54.  
  55. void CoolBase_Binary_Tree::clear () {
  56.   delete root;                    // virtually delete all nodes
  57.   this->root = NULL;
  58.   this->number_nodes = 0;
  59.   this->reset();                // reset state of iterator
  60. }
  61.  
  62.   
  63.  
  64. // calc_depth (recurse thru the Tree and return zero-based depth)
  65. //   if update_bal is not NULL, then the avl balance for this node is
  66. //   updated.  This avl update should be called after balancing the tree
  67. //   as an AVL tree cannot have it's balance othere than -1, 0 1.
  68.  
  69. long CoolBase_Binary_Tree::calc_depth
  70.                 (CoolBase_Binary_Node* node, long depth, Boolean update_bal) {
  71.   if (node == NULL) {                // Null nodes don't count
  72.     if (depth > 0)                        // If not the root
  73.       --depth;                    //   depth bumped 1 too many
  74.     return depth;
  75.   }
  76.   depth++;                    // Do left and right subtrees
  77.   long ldepth = this->calc_depth (node->ltree, depth, update_bal);
  78.   long rdepth = this->calc_depth (node->rtree, depth, update_bal);
  79.  
  80.   // It is an error if rdepth - ldepth is other than -1 0 or 1.
  81.   if (update_bal)                        // If we need to update balance
  82.     node->avl_balance =(int)(rdepth - ldepth);    // it's right tree depth - left
  83.  
  84.   if (ldepth > rdepth)                // Return count of deepest tree
  85.     return ldepth;
  86.   else
  87.     return rdepth;
  88. }
  89.  
  90. // current-node -- Returns node at the current position
  91.  
  92. CoolBase_Binary_Node* CoolBase_Binary_Tree::node () {
  93.   if (this->state.stack.is_empty())
  94.     return NULL;
  95.   else {
  96.     Stack_Entry se = this->state.stack.top();
  97.     return se.get_first();
  98.   }
  99. }
  100.  
  101. // Get the next node in the tree based on the Traversal Type.  This
  102. // maintains a stack of parents in the tree for current position and
  103. // knows how to move forward and backward for preorder, inorder, or
  104. // postorder traversals.  Binary trees only use inorder and inorder_reverse
  105. // so the code for dealing with the other traversal types is commented out
  106. // (almost identical copy of this is in N_Tree)
  107.  
  108. Boolean CoolBase_Binary_Tree::next_internal (Traversal_Type ttype) {
  109.   CoolBase_Binary_Node *node, *ptr1;
  110.   CoolBase_Binary_Node *last_node = NULL;
  111.   Stack_Entry stack_entry;
  112.   int index;
  113.   Boolean forward = TRUE;
  114.  
  115.   switch (ttype) {
  116.   case INORDER_REVERSE:
  117. //case PREORDER_REVERSE:            // Are we going backward?
  118. //case POSTORDER_REVERSE:
  119.     forward = FALSE;
  120.     break;
  121.   }
  122.     
  123.   if (state.stack.is_empty()) {        // If stack is empty
  124.     node = this->root;                //  start with the root
  125.     if (forward)                //  init starting subtree
  126.       index = -1;                //    start at first subtree
  127.     else                    //    or
  128.       index = node->num_subtrees();        //    start at last subtree
  129.     state.stack.push (Stack_Entry (node,index));
  130.     state.forward = forward;
  131.     
  132.   }
  133.   else {                    // Stack has some entries, so
  134.     stack_entry = state.stack.top();        //  get top entry from stack
  135.     node = stack_entry.get_first();        //  load up node
  136.     index = (int)stack_entry.get_second();    //  and subtree index
  137.     last_node = node;                //  remember current position
  138.  
  139.     if (state.forward != forward) {        // Need to modify index
  140.       if (forward)                //  if we've changed direction.
  141.     index--;
  142.       else
  143.     index++;
  144.     }
  145.     state.forward = forward;            // Update direction.
  146.   }
  147.  
  148.   if (forward) {                // Going left to right
  149.     while (TRUE) {                // loop until next node found
  150.       if (++index < node->num_subtrees()) {    // incremented index in range?
  151.     if (node != last_node &&        // If we moved to new node &&
  152.         ((ttype == INORDER  && index == 1)  // Inorder after ltree or
  153. //         ||(ttype == PREORDER && index == 0)// Preorder before ltree
  154.          ))
  155.       return TRUE;                // then this is next node
  156.  
  157.     state.stack.top().set_second(index);    // update stack with new index
  158.     ptr1 = node->subtree(index);        // get node's next subtree
  159.     if (ptr1) {                // When subtree exists
  160.       node = ptr1;                //   point node at subtree
  161.       index = -1;                //   init index for new node
  162.       state.stack.push (Stack_Entry (node, index)); 
  163.     }
  164.       }
  165.       else {                    // No more subtrees for node
  166. //    if (node != last_node &&        // If a new node
  167. //        ttype == POSTORDER) {        //   and Postorder mode, 
  168. //      return TRUE;                //   then this is next node
  169. //    }
  170.     state.stack.pop();// pop this node from stack
  171.     if (state.stack.is_empty())            // Stack empty?
  172.       return FALSE;                //   indicate we're at the end
  173.         else {                    // Stack not empty, so
  174.       stack_entry = state.stack.top();    //  update stack_entry object
  175.       node = stack_entry.get_first(); //  load up node
  176.       index = stack_entry.get_second();    //  and subtree index
  177.     }
  178.       }
  179.     }
  180.   }
  181.  
  182. // This is essesentially the same code as above, but going right to
  183. // left, giving reverse order capability
  184.   else {                                        // Going right to left
  185.     while (TRUE) {                // loop until next node found
  186.       if (--index > -1) {            // decremented index in range?
  187.     if (node != last_node &&        // If we moved to new node &&
  188.         ((ttype == INORDER_REVERSE &&    //  or Inorder_reverse node
  189.           index == 0)             //  is ready to do left subtree
  190. //          || (ttype == POSTORDER_REVERSE &&    //  or Postorder_reverse is
  191. //          index == (node->num_subtrees()-1))  // starting it's subtrees
  192.          ))
  193.       return TRUE;                // then this is next node
  194.     state.stack.top().set_second(index);    // update stack with new index
  195.     ptr1 = node->subtree(index);        // get node's next subtree
  196.     if (ptr1) {                // When subtree exists
  197.       node = ptr1;                //   point node at subtree
  198.       index = node->num_subtrees();        //   init index for new node
  199.       state.stack.push (Stack_Entry (node, index)); 
  200.     }
  201.       }
  202.       else {                    // No more subtrees for node
  203. //    if (node != last_node &&        // If a new node
  204. //        ttype == PREORDER_REVERSE)             //   and Preorder_reverse
  205. //      return TRUE;                //   this is next node
  206.  
  207.     state.stack.pop();            // pop this node from stack
  208.     if (state.stack.is_empty())        // Stack empty?
  209.       return FALSE;                //   indicate we're at the end
  210.         else {                    // Stack not empty, so
  211.       stack_entry = state.stack.top();    //  update stack_entry object
  212.       node = stack_entry.get_first();    //  load up node
  213.       index = (int)stack_entry.get_second();    //  and subtree index
  214.     }
  215.       }
  216.     }
  217.   }
  218. }
  219.  
  220.  
  221.  
  222.  
  223.   // maintain the balance of an AVL tree after a put.  The balance of
  224.   // depths between the right subtree and left subtree are maintained
  225.   // for each node. When this balance differs by more than 1, a single
  226.   // or double rotation is done depending on the constellation to put
  227.   // the balance of that node back to zero.  A single or double
  228.   // rotation on the parent of the inserted node does the job.  Nodes
  229.   // above the parent are not affected.
  230.  
  231. void CoolBase_Binary_Tree::avl_put_balance (BT_Stack &stack) {
  232.   CoolBase_Binary_Node *p1, *p2, *raised_node=NULL;    // alloc tmp ptrs to Node
  233.   CoolBase_Binary_Node *ptr;
  234.   Left_Right route=NONE;
  235.   Boolean more_todo = TRUE;
  236.   while (stack.length() > 0) {            // Loop thru nodes on stack
  237.     Stack_Entry stack_entry = stack.pop();    // Pop next stack_entry
  238.     ptr = stack_entry.get_first();        // Get Node 
  239.     route = (Left_Right)stack_entry.get_second();// Get the subtree
  240.     if (raised_node != NULL) {            // A node was rotated up
  241.       if (route == LEFT)            // For a left route
  242.     ptr->ltree = raised_node;        //  change ltree to raised node
  243.       else if (route == RIGHT)            // or for right route
  244.     ptr->rtree = raised_node;        //  change rtree to raised node
  245.       raised_node = NULL;
  246.     }
  247.     if (more_todo == FALSE)            // Exit loop when all balanced
  248.       break;
  249.     
  250.     if (route == LEFT) {            // Node inserted as an LTREE
  251.       switch (ptr->avl_balance) {        // Depending on node's balance
  252.       case 1:
  253.     ptr->avl_balance = 0;            // Set node as balanced
  254.     more_todo = FALSE;
  255.     break;
  256.       case 0:
  257.     ptr->avl_balance = -1;            // Set node as 1 heavy on left
  258.     break;
  259.       case -1:                    // Will need to rotate
  260.     more_todo = FALSE;
  261.     p1 = ptr->ltree;            
  262.     if (p1->avl_balance == -1) {        // Single Right Rotation
  263.       ptr->ltree = p1->rtree;
  264.       p1->rtree = ptr;
  265.       p1->avl_balance = 0;
  266.       ptr->avl_balance = 0;
  267.       raised_node = p1;            // This node bubbled up
  268.     }                    // End Single right rotation
  269.     else {                    // Double Right Rotation
  270.       p2 = p1->rtree;
  271.       p1->rtree = p2->ltree;
  272.       p2->ltree = p1;
  273.       ptr->ltree = p2->rtree;
  274.       p2->rtree = ptr;
  275.       if (p2->avl_balance == -1)        // update balance for ptr
  276.         ptr->avl_balance = 1;
  277.       else
  278.         ptr->avl_balance = 0;
  279.       if (p2->avl_balance == 1)        // update balance for p1
  280.         p1->avl_balance = -1;
  281.       else
  282.         p1->avl_balance = 0;
  283.       p2->avl_balance = 0;            // update balance for p2
  284.       raised_node = p2;            // This node now moved up
  285.       break;
  286.     }                    // End Left Right Rotation
  287.       }                        // End switch
  288.     }                        // End LTREE path
  289.     
  290.     else {                    // Node inserted as an RTREE
  291.       switch (ptr->avl_balance) {
  292.       case -1:
  293.     ptr->avl_balance = 0;            // Node is now balanced
  294.     more_todo = FALSE;            // Tree is now balanced
  295.     break;
  296.       case 0:
  297.     ptr->avl_balance = 1;            // Node is 1 heavy on right
  298.     break;
  299.       case 1:                    // Will need to rotate
  300.     more_todo = FALSE;
  301.     p1 = ptr->rtree;
  302.     if (p1->avl_balance == 1) {        // Single Left Rotation
  303.       ptr->rtree = p1->ltree;
  304.       p1->ltree = ptr;
  305.       p1->avl_balance = 0;
  306.       ptr->avl_balance = 0;
  307.       raised_node = p1;
  308.     }                    // End Single Left Rotation
  309.     else {                    // Right/Left Rotation
  310.       p2 = p1->ltree;
  311.       p1->ltree = p2->rtree;
  312.       p2->rtree = p1;
  313.       ptr->rtree = p2->ltree;
  314.       p2->ltree = ptr;
  315.       if (p2->avl_balance == 1)        // Update balance for ptr
  316.         ptr->avl_balance = -1;
  317.       else
  318.         ptr->avl_balance = 0;
  319.       if (p2->avl_balance == -1)        // Update balance for p1
  320.         p1->avl_balance = 1;
  321.       else
  322.         p1->avl_balance = 0;
  323.       p2->avl_balance = 0;            // update balance for p2
  324.       raised_node = p2;            // This node now moved up
  325.       break;
  326.     }                    // End Right/Left Rotation
  327.       }                        // End switch
  328.     }                        // End RTREE path
  329.   }
  330.  
  331.   if (raised_node != NULL) {            // When a node gets raised
  332.     this->root = raised_node;            //  raised_node to be root
  333.   }
  334. }
  335.  
  336. // Balances the nodes in the path of a removed node for an AVL Binary Tree
  337. // The parent nodes and index to their subtrees are maintained in a Stack of 
  338. // Stack_entrys
  339.  
  340. void CoolBase_Binary_Tree::avl_remove_balance (BT_Stack &stack) {
  341.   CoolBase_Binary_Node *p, *p1, *p2, *raised_node=NULL;    // Temporary pointers to nodes
  342.   Boolean more_todo=TRUE;            // When more_todo is FALSE, done.
  343.   Left_Right route=NONE;
  344.   while (stack.length() > 0) {            // Loop thru nodes on stack
  345.     Stack_Entry stack_entry = stack.pop();    // Get next stack_entry
  346.     p = stack_entry.get_first();        // Get Node 
  347.     route = (Left_Right)stack_entry.get_second();// Get the subtree
  348.  
  349.     // UPDATE PARENT TO POINT AT RAISED NODE FROM PREVIOUS ITERATION
  350.     if (raised_node != NULL) {            // If there is a raised node
  351.       if (route == LEFT)            //    See what side was changed
  352.       p->ltree = raised_node;        //    Update ltree
  353.       else
  354.     p->rtree = raised_node;            //    or update rtree
  355.       raised_node = NULL;            //    raised_node taken care of.
  356.     }
  357.  
  358.     if (more_todo == FALSE)            // Tree is balanced
  359.       break;
  360.  
  361.     // BALANCE LEFT SUBTREE OF NODE P.  Note that this is VERY similar 
  362.     // to the code below to balance the right side.  Changes here are likely
  363.     // necessary below also.
  364.  
  365.     if (route == LEFT) {
  366.       switch (p->avl_balance) {
  367.       case -1:                    // Set balance to 0. 
  368.     p->avl_balance = 0;            //   balance parent node
  369.     break;
  370.       case 0:                    // Set balance to 1.  Tree is 
  371.     p->avl_balance = 1;            //   all balanced.
  372.     more_todo = FALSE;
  373.     break;
  374.       case 1:                    // Need to rotate
  375.     p1 = p->rtree;
  376.     if (p1->avl_balance >= 0) {        
  377.       p->rtree = p1->ltree;            // Single left rotate
  378.       p1->ltree = p;
  379.       raised_node = p1;
  380.       if (p1->avl_balance == 0) {        // Update p and p1 balance
  381.         p->avl_balance = 1;
  382.         p1->avl_balance = -1;
  383.         more_todo = FALSE;
  384.       }
  385.       else {
  386.         p->avl_balance = 0;
  387.         p1->avl_balance = 0;
  388.       }
  389.     }
  390.     else {                    // Double right left rotate
  391.       p2 = p1->ltree;
  392.       p1->ltree = p2->rtree;
  393.       p2->rtree = p1;
  394.       p->rtree = p2->ltree;
  395.       p2->ltree = p;
  396.       int b2 = p2->avl_balance;
  397.       if (b2 == 1)                // Set new balance for node p
  398.         p->avl_balance = -1;
  399.       else
  400.         p->avl_balance = 0;
  401.       if (b2 == -1)                // Set new balance for node p1
  402.         p1->avl_balance = 1;
  403.       else 
  404.         p1->avl_balance = 0;
  405.  
  406.       p2->avl_balance = 0;            // Set new balance for node p2
  407.       raised_node = p2;        
  408.     }
  409.       }
  410.     }
  411.     // BALANCE RIGHT SUBTREE OF NODE P.  Note that this is VERY similar
  412.     // to the code above to balance the left side.  Changes here are likely
  413.     // necessary above also.
  414.     else {
  415.       switch (p->avl_balance) {
  416.       case 1:                    // Set balance to 0. 
  417.     p->avl_balance = 0;            //   balance parent node
  418.     break;
  419.       case 0:                    // Set balance to 1.  Tree is 
  420.     p->avl_balance = -1;            //   all balanced.
  421.     more_todo = FALSE;
  422.     break;
  423.       case -1:                    // Need to rotate
  424.     p1 = p->ltree;
  425.     if (p1->avl_balance <= 0) {        // Single right rotate
  426.       p->ltree = p1->rtree;
  427.       p1->rtree = p;
  428.       raised_node = p1;
  429.       if (p1->avl_balance == 0) {        // Update p and p1 balance
  430.         p->avl_balance = -1;
  431.         p1->avl_balance = 1;
  432.         more_todo = FALSE;            
  433.       }
  434.       else {
  435.         p->avl_balance = 0;
  436.         p1->avl_balance = 0;
  437.       }
  438.     }
  439.     else {                    // Double left right rotate
  440.       p2 = p1->rtree;
  441.       p1->rtree = p2->ltree;
  442.       p2->ltree = p1;
  443.       p->ltree = p2->rtree;
  444.       p2->rtree = p;
  445.       int b2 = p2->avl_balance;
  446.       if (b2 == -1)                // Set new balance for node p
  447.         p->avl_balance = 1;
  448.       else
  449.         p->avl_balance = 0;
  450.       if (b2 == 1)                // Set new balance for node p1
  451.         p1->avl_balance = -1;
  452.       else
  453.         p1->avl_balance = 0;
  454.  
  455.       p2->avl_balance = 0;            // Set new balance for node p2
  456.       raised_node = p2;
  457.     }
  458.       }
  459.     }
  460.   }
  461.  
  462.   // If raised_node is non_null, after all the balancing is done, it means
  463.   // we have a new root. 
  464.   if (raised_node != NULL) {
  465.     this->root = raised_node;
  466.   }
  467. }
  468.               
  469.  
  470. // curpos_error -- Raise exception for invalid current position
  471. // Input:         Character string of function and type
  472. // Output:        None
  473.  
  474. void CoolBase_Binary_Tree::curpos_error (const char* Type, const char* fcn) {
  475.   //RAISE Error, SYM(CoolBase_Binary_Tree), SYM(Invalid_Cpos),
  476.   printf ("CoolBase_Binary_Tree<%s>::%s: Invalid current position.\n", Type, fcn);
  477.   abort ();
  478. }
  479.  
  480.  
  481.  
  482.